package com.jia.leetCode;

import java.util.ArrayList;
import java.util.List;

/**
 * 173.二叉搜索树迭代器
 实现一个二叉搜索树迭代器。你将使用二叉搜索树的根节点初始化迭代器。

 调用 next() 将返回二叉搜索树中的下一个最小的数。
 */
public class Pro0173 {
    List<TreeNode> list;
    int index;
    public Pro0173(TreeNode root) {
        this.list = new ArrayList<>();
        this.index = 0;
        inorder(root);
    }
    private void inorder(TreeNode node){
        if(node == null) return;
        inorder(node.left);
        this.list.add(node);
        inorder(node.right);
    }

    /** @return the next smallest number */
    public int next() {
        if(index < 0 || index >= list.size()) throw new RuntimeException("out of index");
        return list.get(index++).val;
    }

    /** @return whether we have a next smallest number */
    public boolean hasNext() {
        return index < list.size();
    }
}
